package com.example.code.class01;

/**
 * @Date 2022/7/12
 * @Created by Jonathan
 */
public class Code07_TargetSum {
    public static void main(String[] args) {
        // 1 2 4
        // 3 4
        // 2 5

        int[] arr = new int[]{1, 2, 3, 4, 5};
        final int result = getResult(arr, 3);
        System.out.println(result);
    }


    private static int getResult(int[] arr, int target) {
        return process(arr, 0, target);
    }


    private static int process(int[] arr, int index, int rest ) {
        if (index == arr.length) {
            return rest == 0 ? 1 : 0;
        }
        // 要index位置的凑成的方法
        int res = 0;
        res += process(arr, index + 1, rest - arr[index]);
        // 加上不要index位置凑成的方法
        res += process(arr, index + 1, rest + arr[index]);
        return res;
    }
}
